package FindKPairswithSmallestSums;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
	class Node{
		private int num1;
		private int num2;
		private int sum;
	}
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Node> list=new PriorityQueue<Node>((Node o1,Node o2)->(Integer.compare(o1.sum, o2.sum)));
        List<int[]> result=new ArrayList<>();
        if (nums1==null || nums2==null || nums1.length ==0 || nums2.length ==0) return result;
        for (int i=0;i<nums2.length;i++){
        	Node node=new Node();
        	node.num1=0;
        	node.num2=i;
        	node.sum=nums1[0]+nums2[i];
        	list.offer(node);
        }
        
        for (int i=1;i<=k;i++){
        	Node node=list.poll();
        	int[] t={nums1[node.num1],nums2[node.num2]};
        	result.add(t);
        	if (node.num1+1<nums1.length){
        		Node newNode=new Node();
        		newNode.num1=node.num1+1;
        		newNode.num2=node.num2;
        		newNode.sum=nums1[newNode.num1]+nums2[newNode.num2];
        		list.offer(newNode);
        	}
        	else{
        		if (list.isEmpty()) break;
        	}
        }
        return result;
}
    public static void main(String args[]) {
    	int[] nums1={1,1,2};
    	int[] nums2={1,2,3};
    	Solution so=new Solution();
    	so.kSmallestPairs(nums1, nums2, 10);
    	
		
	}
}
